package problem230

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

var index = 0
var result = 0

func kthSmallest(root *TreeNode, k int) int {
	index = 0
	result = 0
	traverse(root, k)
	return result
}

func traverse(root *TreeNode, k int) bool {
	if root == nil {
		return true
	}
	if !traverse(root.Left, k) {
		return false
	}
	index++
	if index == k {
		result = root.Val
		return false
	}
	if !traverse(root.Right, k) {
		return false
	}
	return true
}

func main() {
	root := &TreeNode{
		Val: 3,
		Left: &TreeNode{
			Val: 1,
			Right: &TreeNode{
				Val: 2,
			},
		},
		Right: &TreeNode{
			Val: 4,
		},
	}
	ret := kthSmallest(root, 1)
	println(ret)
}
